package main

import (
	"fmt"
	"slices"
)

// 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
func merge(intervals [][]int) [][]int {
	//二维数组先按照左端排序
	count := len(intervals)
	for i := 0; i < count; i++ {
		min := intervals[i] // 保存当前最小值
		for j := i + 1; j < count; j++ {
			if intervals[j][0] < min[0] {
				intervals[i], intervals[j] = intervals[j], min
				min = intervals[i] // 更新min为新的最小值
			}
		}
	}
	//开始合并数组
	newSlice := make([][]int, 0)
	newSlice = append(newSlice, intervals[0])
	a := 0
	for i := 1; i < len(intervals); i++ {
		if newSlice[a][1] >= intervals[i][0] {
			pre := newSlice[a][1]
			after := intervals[i][1]
			if pre > after {
				newSlice[a][1] = pre
			} else {
				newSlice[a][1] = after
			}
			fmt.Printf("第%d轮后: %v\n", i+1, intervals)
		} else {
			newSlice = append(newSlice, intervals[i])
			fmt.Printf("第%d轮后新数组: %v\n", i+1, newSlice)
			a++
		}
	}
	return newSlice
}

// 官方解法
func merge1(intervals [][]int) (ans [][]int) {
	slices.SortFunc(intervals, func(p, q []int) int { return p[0] - q[0] }) // 按照左端点从小到大排序
	for _, p := range intervals {
		m := len(ans)
		if m > 0 && p[0] <= ans[m-1][1] { // 可以合并
			ans[m-1][1] = max(ans[m-1][1], p[1]) // 更新右端点最大值
		} else { // 不相交，无法合并
			ans = append(ans, p) // 新的合并区间
		}
	}
	return
}

func main() {
	a := [][]int{{1, 3}, {8, 10}, {2, 6}, {15, 18}}
	merge(a)
}
